package com.fjl.array.leetcode220;

import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeSet;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/3/25 14:36
 */
/*
给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。
找出满足下述条件的下标对 (i, j)：
i != j,
abs(i - j) <= indexDiff
abs(nums[i] - nums[j]) <= valueDiff
如果存在，返回 true ；否则，返回 false 。
示例 1：
    输入：nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
    输出：true
    解释：可以找出 (i, j) = (0, 3) 。
    满足下述 3 个条件：
    i != j --> 0 != 3
    abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
    abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0
示例 2：
    输入：nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
    输出：false
    解释：尝试所有可能的下标对 (i, j) ，均无法满足这 3 个条件，因此返回 false 。
 */
public class Clazz {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        TreeSet<Integer> window = new TreeSet<>();
        int left = 0, right = 0;
        // 滑动窗口算法框架，维护一个大小为 k 的窗口
        while (right < nums.length) {
            // 为了防止 i == j，所以在扩大窗口之前先判断是否有符合题意的索引对 (i, j)
            // 查找略大于 nums[right] 的那个元素
            Integer ceiling = window.ceiling(nums[right]);// 找 ≥nums[right] 的最小元素
            if (ceiling != null && (long) ceiling - nums[right] <= valueDiff) {
                return true;
            }
            // 查找略小于 nums[right] 的那个元素
            Integer floor = window.floor(nums[right]);// 找 ≤15 的最大元素
            if (floor != null && (long) nums[right] - floor <= valueDiff) {
                return true;
            }
            // 扩大窗口
            window.add(nums[right]);
            right++;
            if (right - left > indexDiff) {
                // 缩小窗口
                window.remove(nums[left]);
                left++;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(new Clazz().containsNearbyAlmostDuplicate(new int[]{1,2,2,3,4,5}, 3, 0));
    }
}
